/*
 * @lc app=leetcode.cn id=1 lang=golang
 *
 * [1] 两数之和
 */

// 2-2. 哈希, 和2-1只是for循环时语法不同
// 时间 O(n)
// 空间 O(n)
// @lc code=start
func twoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for i, v := range nums {
		if j, ok := m[target-v]; ok {
			return []int{i, j}
		}
		m[v] = i
	}

	return []int{}
}

// @lc code=end

// 2-1. 哈希
// 时间 O(n)
// 空间 O(n)
// @lc code=start
func twoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		if j, ok := m[target-nums[i]]; ok {
			return []int{i, j}
		}
		m[nums[i]] = i
	}

	return []int{}
}

// @lc code=end

// 1. 暴力枚举
// 时间 O(n^2)
// 空间 O(1)
// @lc code=start
func twoSum(nums []int, target int) []int {
	for i := 0; i < len(nums)-1; i++ {
		for j := i + 1; j < len(nums); j++ {
			if (nums[i] + nums[j]) == target {
				return []int{i, j}
			}
		}
	}

	return []int{}
}

// @lc code=end

